package NO18;

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * @author swg
 *
 */
public class HasSubtree {
	
	public class TreeNode {
	    int val = 0;
	    TreeNode left = null;
	    TreeNode right = null;

	    public TreeNode(int val) {
	        this.val = val;

	    }

	}
	
	public class Solution {
	    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
	        boolean result = false;
	        
	        if(root1 != null && root2 != null){
	            if(root1.val == root2.val){
	                //根结点匹配的话，比较下面的节点是否都相等
	                result = tree1ConstainsTree2(root1,root2);
	            }
	            
	            //根结点不匹配,直接更换左子节点或者右子节点再进行比较
	            if(!result){
	                result = HasSubtree(root1.left,root2);
	            }
	            
	            if(!result){
	                result = HasSubtree(root1.right,root2);
	            }
	        }
	        return result; 
	    }
	    
	    private boolean tree1ConstainsTree2(TreeNode root1,TreeNode root2){
	        //如果子树已经遍历完毕，说明是其字树
	        if(root2 == null){
	            return true;
	        }
	        //如果子树还没被遍历完毕，但是A树已经遍历完毕，说明不是其子树
	        if(root1 == null){
	            return false;
	        }
	        //值不一样，肯定不是其子树
	        if(root1.val != root2.val){
	            return false;
	        }
	        //递归比较子节点是否相等
	        return tree1ConstainsTree2(root1.left,root2.left) && tree1ConstainsTree2(root1.right,root2.right); 
	    }
	}
}
